Decomposition of Cyclic Groups

Theorem

Given two cyclic groups \(C_m\) and \(C_n\) of order \(m\) and \(n\) respectively, if \(\mathrm{gcd}(m, n) = 1\) then

\[ C_m \otimes C_n \cong C_{mn}.\]

Proof

We will prove that \(C_m \otimes C_n\) is cyclic by showing that for generator \(g_m\) of \(C_m\) and \(g_n\) of \(C_n\)

\[ (g_m, g_n)\]

is a generator of \(C_m \otimes C_n\) of order \(mn\).

First note that

\[ (g_m, g_n)^{k} = (g_m^{k}, g_n^{k}).\]

and hence we end up with the identity if \(m \mid k\) and \(n \mid k\).

The smallest possible value which is a multiple of both \(m\) and \(n\) is their lowest common multiple by definition. However, since \(\mathrm{gcd}(m, n) = 1\), we conclude by this result (\(\gcd(m, n) \cdot \mathrm{lcm}(m, n) = mn\)) that

\[ \mathrm{lcm}(m, n) = mn.\]

This then gives us that

\[ \phi : g^k \mapsto (g_m^k, g_n^k)\]

is the explicit isomorphism between these groups.

Corollary

If \(m\) and \(n\) are coprime integers positive integers, then:

\[ \mathbb{Z}_{mn} \cong \mathbb{Z}_m \oplus \mathbb{Z}_n\]

where \(\oplus\) gives the direct sum of groups.

This result is also known as the chinese remainder theorem, and follows very easily from the fact that \(\mathbb{Z}_m\) is cyclic of order \(m\), generated by \(1\).

We can also get an explicit isomorphism by means of the group as direct product of subgroups, as shown below, however note that this isomorphism is different to the one given by the chinese remainder theorem, and thus is no replacement for the chinese remainder theorem algorithm.

Proof

The key idea in this alternate proof is identifying that for coprime \(m\) and \(n\), we can decompose

\[ \mathbb{Z}_{mn} \cong \langle \frac{mn}{m} \rangle \oplus \langle \frac{mn}{n} \rangle \cong \mathbb{Z}_n \oplus \mathbb{Z}_m.\]

This is very intuitive with an example:

\[\begin{align*} \mathbb{Z}_{15} \cong \langle 3 \rangle \oplus \langle 5 \rangle. \end{align*}\]

Note that \(\langle 3 \rangle = \{0, 3, 6, 9, 12\}\) and has \(5\) elements. This is isomorphic to \(\mathbb{Z}_5\) using the isomorphism

\[ a \mapsto 3a.\]

Similarly for \(\langle 5 \rangle\) and \(\mathbb{Z}_3\).

To prove this rigorously, we appeal to this corollary of the internal characterisation of products, and note that coprimality guarantees the trivial intersection (no multiple of \(a\) can be a multiple of \(b\) unless it is a multiple of \(ab\) for coprime \(a\) and \(b\)) while the way the groups are chosen means the product of their sizes is equal to the size of the main group.

Crucially though, the isomorphism given from this theorem is different to that of the chinese remainder theorem.

Specifically, if we have

\[ x \equiv 2 \pmod 3 \quad \text{and} \quad x \equiv 4 \pmod 5,\]

this corresponds with \(2 \times 5 = 10\) in \(\langle 5 \rangle\) and \(4 \times 3 = 12\) in \(\langle 3 \rangle\), however when we apply the isomorphism back to \(\mathbb{Z}_{15}\),

\[ \phi((12, 10)) = 22 \pmod 15 = 7,\]

we do not get the solution to the original equations. There is automorphism that maps these values back to the desired solutions.

Hence in this case while we have an explicit isomorphism, it's not a particularly useful one.